﻿// 0926train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <numeric>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
小组中每个人都有一张卡片，卡片上是6位以内的正整数，组员将卡片连起来可以组成多种数字
计算可以组成的最大数字。

输入
由,分割的多个正整数字符串，不需要考虑非数字异常情况。小组中最多有25个人

输出描述
最大数字字符串

输入
22,221
输出
22221

输入
4589,101,41425,9999
输出
9999458941425101
 */
class Solution01
{
public:
    Solution01(vector<string>&str_vec)
    {
        sort(str_vec.begin(), str_vec.end(), [](string&str_1,string&str_2)
            {
                return str_1 + str_2 > str_2 + str_1;
            });

        string result;
        for (auto&str:str_vec)
        {
            result += str;
        }
        cout << result;
	    //Solution01
    }
};


/*
 m代替手速，即每次下手捞菜后至少要过m秒才能再捞（每次只能捞一个）
 那么用最合理的策略，最多能吃到多少刚好合适的菜

输入描述
第一行两个整数n，m。其中n代表往锅里下菜的个数，m代表手速。
接下来有n行，每行有两个数x，y。代表第x秒下的菜过y秒才能变得刚好合适

输出描述
输出一个整数代表用最合理的策略，最多能吃到刚好合适的菜的数量。

示例1
2 1
1 2
2 1
输出
1
一共下了两个菜，在第一秒下的菜，需要到第三秒吃
在第二秒下的菜，也要到第三秒吃，所以只能吃一个

3 1
1 2
1 3
2 3
输出
3
 */
class Solution02
{
public:
    Solution02(vector<vector<int>>&num_vec, int min_diff)
    {
        unordered_set<int>choose_set;

        for (auto&item:num_vec)
        {
            choose_set.insert(item[0] + item[1]);
        }

        vector<int>kind_v;
        for (auto&item:choose_set)
        {
            kind_v.push_back(item);
        }

        sort(kind_v.begin(), kind_v.end());

        int result = 1;
        int prev = kind_v[0];

        int kind_size = kind_v.size();
        for (int i=1; i<kind_size; i++)
        {
	        if (kind_v[i]-prev>=min_diff)
	        {
                result += 1;
                prev = kind_v[i];
	        }
        }

        cout << result;
        //Solution02
    }
};


/*
在一条笔直的公路上安装了N个路灯，从位置0开始安装，路灯之间间距固定为100米
每个路灯都有自己的照明半径，请计算第一个路灯和最后一个路灯之间，无法照明的区间的长度和
注意：
除了第一个和最后一个路灯，第i个路灯的照明区域为[100*i-r, 100*i+r]，
即照明半径表示该路灯其前后区域都能照明。

输入描述
第一行为一个数N，表示路灯个数，1 <= N <= 100000
第二行为N个空格分隔的数，表示路灯的照明半径，1 <= 照明半径 <= 100000*100

输出描述
第一个路灯和最后一个路灯之间，无法照明的区间的长度和

输入
4
50 70 20 70
输出
20
路灯1 覆盖0-50，路灯2 覆盖30-170，路灯3覆盖180-220，路灯4覆盖230-370
没覆盖的区域是170-180和220-230，一共20米
 */
class Solution03
{
public:
    Solution03(vector<int>&num_vec)
    {
        int v_size = num_vec.size();
        vector<vector<int>>intervals(v_size);
        //100*i-r, 100*i+r
        for (int i=0; i<v_size; i++)
        {
            vector<int>item_v(2);
            int start = 100 * i - num_vec[i];
            start = max(0, start);
            int end = 100 * i + num_vec[i];
            if (i-1>=0)
            {
                end = max(intervals[i - 1][1], end);
                intervals[i - 1][0] = min(start, intervals[i - 1][0]);
            }
            item_v[0] = start;
            item_v[1] = end;
            intervals[i] = item_v;
            //for---
        }

        

        int result = 0;
        //累加区间空隙
        for (int i=1; i<v_size; i++)
        {
            int last_end = intervals[i-1][1];
            int curr_start = intervals[i][0];

            if (curr_start>last_end)
            {
                result += curr_start - last_end;
            }
        }

        cout << result;
	    //Solution03
    }
};


/*
有一个荒岛，只有左右两个港口，现在有一群人需要从两个港口逃生，
有的人往右逃生，有的往左逃生，如果两个人相遇，则 pk，
体力值大的能够打赢体力值小的，体力值相同则同归于尽，赢的人才能继续往前逃生，并减少相应的体力

输入描述
系列非 0 整数，用空格隔开，正数代表向右逃生，负数代表向左逃生
输出描述
最终能够逃生的人构成的序列

输入
5 10 8 -8 -5
输出
5 5

8 与 -8 相遇，同归于尽，10 遇到-5，打赢并减少五点体力，最终逃生的为[5，5]，均从右侧港口逃生
 */
class Solution04
{
public:
    Solution04(vector<int>&num_vec)
    {
        vector<int>stack_v;
        //>0，往右的直接入栈
        //<0，往左的，栈顶<0，直接入栈
        //如果栈顶>0，持续弹出栈顶消耗当前
        int v_size = num_vec.size();
        for (int i=0; i< v_size; i++)
        {
            int curr = num_vec[i];
            if (curr > 0)
            {
                stack_v.push_back(curr);
                continue;
            }

            int remain = abs(curr);
            while (!stack_v.empty() && stack_v.back()>0)
            {
                if (stack_v.back()>remain)
                {
                    stack_v.back() -= remain;
                    remain = 0;
                    break;
                }
            	if (stack_v.back()==remain)
                {
                    remain = 0;
                    stack_v.pop_back();
                    break;
                }

                remain -= stack_v.back();
                stack_v.pop_back();
	            //while---
            }
            if (remain!=0)
            {
                remain = remain * (-1);
                stack_v.push_back(remain);
            }

        }

        for (auto&num:stack_v)
        {
            cout << num << ' ';
        }

	    //Solution04
    }
};


/*
题目描述
给一个数组，数组里面都是代表非负整数的字符串，将数组里所有的数值排列组合拼接起来组成一个数字，
输出拼成的最小的数字

输入描述
一个数组，数组不为空，数组里面都是代表非负整数的字符串，可以是0开头，
例如:["13", "045","09", "56"]
数组的大小范围：[1,50]
数组中每个元素的长度范围：[1,30]

输出描述：
以字符串的格式输出一个数字，如果最终结果是多位数字，
要优先选择输出不是“0”开头的最小数字:如果拼接出的数字都是“0”开头，
则选取值最小的，并且把开头部分的“0”都去掉再输出;
如果是单位数“0”，可以直接输出“0”

示例1
输入：
20 1
输出：
120
示例2
输入：
08 10 2
输出：
10082

08 02 001

输入
12 121
输出
12112
 */
class Solution05
{
public:
    static bool compare(string&str_1, string&str_2)
    {
        if (str_1 == str_2) return false;

        int min_size = min(str_1.size(), str_2.size());

        for (int i=0; i<min_size; i++)
        {
            if (str_1[i] < str_2[i]) return true;
            if (str_1[i] > str_2[i]) return false;
        }

        pair<string, int>min_str = make_pair(str_1, 1);
        pair<string, int>max_str = make_pair(str_2, 2);

        if (str_1.size()>str_2.size())
        {
            min_str = make_pair(str_2, 2);
            max_str = make_pair(str_1, 1);
        }

        pair<string, int>remain_str = max_str;
        remain_str.first = remain_str.first.substr(min_size);

        int result = 1;
        bool is_result = false;
        int remain_size = min(remain_str.first.size(), min_str.first.size());
        for (int i=0; i<remain_size; i++)
        {
            if (remain_str.first[i]<min_str.first[i])
            {
                result = remain_str.second;
                is_result = true;
                break;
            }
            if (min_str.first[i]<remain_str.first[i])
            {
                result = min_str.second;
                is_result = true;
                break;
            }
        }
        if (is_result)
        {
            return result == 1;
        }
        return str_1.size() < str_2.size();

	    //compare
    }

    static bool compareReal(pair<string, string>&p_1, pair<string, string>& p_2)
    {
        if (p_1.first == p_2.first) return false;
        int min_size = min(p_1.first.size(), p_2.first.size());

        for (int i = 0; i < min_size; i++)
        {
            if (p_1.first[i] < p_2.first[i]) return true;
            if (p_1.first[i] > p_2.first[i]) return false;
        }

        pair<string, int>min_str = make_pair(p_1.first, 1);
        pair<string, int>max_str = make_pair(p_2.first, 2);

        if (p_1.first.size() > p_2.first.size())
        {
            min_str = make_pair(p_2.first, 2);
            max_str = make_pair(p_1.first, 1);
        }

        pair<string, int>remain_str = max_str;
        remain_str.first = remain_str.first.substr(min_size);

        int result = 1;
        int remain_size = min(remain_str.first.size(), min_str.first.size());
        for (int i = 0; i < remain_size; i++)
        {
            if (remain_str.first[i] < min_str.first[i])
            {
                result = remain_str.second;
                break;
            }
            if (min_str.first[i] < remain_str.first[i])
            {
                result = min_str.second;
                break;
            }
        }
        return result == 1;

        //compare
    }

    Solution05(vector<string>&str_vec)
    {
        //["13", "045","09", "56"]
        //把非0开头筛选出来，找到最合适的头部
        string result;
        if (str_vec.size() == 1)
        {
            result = str_vec[0];
            if (result == "0")
            {
                cout << result;
                return;
            }
            while (result[0] == '0')
            {
                result = result.substr(1);
            }
            if (result.empty())
            {
                cout << "0";
                return;
            }
            cout << result;
            return;
        }


        vector<string>tail_v;
        for (auto& str : str_vec)
        {
            if (str[0] != '0')
            {
                tail_v.push_back(str);
            }
        }
        if (!tail_v.empty())
        {
            sort(tail_v.begin(), tail_v.end(), compare);
            result += tail_v[0];
            vector<string>new_vec;
            for (auto& str : str_vec)
            {
                if (str == tail_v[0])
                {
                    continue;
                }
                new_vec.push_back(str);
            }
            str_vec = new_vec;
        }
        else
        {
	        //说明全部都是0开头的，那么要把0去掉，看看哪个小
            vector<pair<string, string>>tail_0_v;
            for (auto&str:str_vec)
            {
                if (str == "0") continue;
                string real = str;
                while (real[0]=='0')
                {
                    real = real.substr(1);
                }
                if (real.empty()) continue;
                tail_0_v.push_back(make_pair(real, str));
            }
            if (!tail_0_v.empty())
            {
                sort(tail_0_v.begin(), tail_0_v.end(), compareReal);
                string tail_str = tail_0_v[0].second;
                result += tail_str;

                vector<string>new_vec;
                for (auto& str : str_vec)
                {
                    if (str == tail_str) continue;
                    new_vec.push_back(str);
                }
                str_vec = new_vec;
            }
        }
        
        sort(str_vec.begin(), str_vec.end(), compare);

    	for (auto&str:str_vec)
        {
            result += str;
        }

        if (result=="0")
        {
            cout << result;
            return;
        }
        while (result[0]=='0')
        {
            result = result.substr(1);
        }
        if (result.empty())
        {
            cout << "0";
            return;
        }
        cout << result;

	    //Solution05
    }
};

class Solution15
{
public:
    static bool compare(string& str_1, string& str_2)
    {
        return str_1 + str_2 < str_2 + str_1;

        //compare
    }

    static bool compareReal(pair<string, string>& p_1, pair<string, string>& p_2)
    {
        return p_1.first + p_2.first < p_2.first + p_1.first;
        //compare
    }

    Solution15(vector<string>& str_vec)
    {
        //["13", "045","09", "56"]
        //把非0开头筛选出来，找到最合适的头部
        string result;
        if (str_vec.size() == 1)
        {
            result = str_vec[0];
            if (result == "0")
            {
                cout << result;
                return;
            }
            while (result[0] == '0')
            {
                result = result.substr(1);
            }
            if (result.empty())
            {
                cout << "0";
                return;
            }
            cout << result;
            return;
        }


        vector<string>tail_v;
        for (auto& str : str_vec)
        {
            if (str[0] != '0')
            {
                tail_v.push_back(str);
            }
        }
        if (!tail_v.empty())
        {
            sort(tail_v.begin(), tail_v.end(), compare);
            result += tail_v[0];
            vector<string>new_vec;
            for (auto& str : str_vec)
            {
                if (str == tail_v[0])
                {
                    continue;
                }
                new_vec.push_back(str);
            }
            str_vec = new_vec;
        }
        else
        {
            //说明全部都是0开头的，那么要把0去掉，看看哪个小
            vector<pair<string, string>>tail_0_v;
            for (auto& str : str_vec)
            {
                if (str == "0") continue;
                string real = str;
                while (real[0] == '0')
                {
                    real = real.substr(1);
                }
                if (real.empty()) continue;
                tail_0_v.push_back(make_pair(real, str));
            }
            if (!tail_0_v.empty())
            {
                sort(tail_0_v.begin(), tail_0_v.end(), compareReal);
                string tail_str = tail_0_v[0].second;
                result += tail_str;

                vector<string>new_vec;
                for (auto& str : str_vec)
                {
                    if (str == tail_str) continue;
                    new_vec.push_back(str);
                }
                str_vec = new_vec;
            }
        }

        sort(str_vec.begin(), str_vec.end(), compare);

        for (auto& str : str_vec)
        {
            result += str;
        }

        if (result == "0")
        {
            cout << result;
            return;
        }
        while (result[0] == '0')
        {
            result = result.substr(1);
        }
        if (result.empty())
        {
            cout << "0";
            return;
        }
        cout << result;

        //Solution15
    }
};

int main()
{
	{
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        vector<string>str_vec;
        while (getline(oh_sstream, token, ','))
        {
            str_vec.push_back(token);
        }
        Solution01 solu(str_vec);
        return 0;
	}
	{
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        vector<string>str_vec;
        while (oh_sstream>>token)
        {
            str_vec.push_back(token);
        }

        //Solution05 solu(str_vec);
        Solution15 solu(str_vec);

        return 0;
	}
	{
        //5 10 8 -8 -5
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        vector<int>num_vec;
        while (oh_sstream>>token)
        {
            num_vec.push_back(stoi(token));
        }

        Solution04 solu(num_vec);

        return 0;
	}
	{
/*
4
50 70 20 70
*/
        int v_size;
        cin >> v_size;

        vector<int>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }

        Solution03 solu(num_vec);

        return 0;
	}
	{
        int v_size, min_diff;
        cin >> v_size >> min_diff;

        vector<vector<int>>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            vector<int>item(2);
            cin >> item[0]>>item[1];
            num_vec[i] = item;
        }

        Solution02 solu(num_vec, min_diff);

        return 0;
	}
    string input;
    getline(cin, input);
    stringstream oh_sstream(input);
    string token;
    vector<string>str_vec;
    while (getline(oh_sstream, token, ','))
    {
        str_vec.push_back(token);
    }
    Solution01 solu(str_vec);



}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
